The present invention relates to a system and method for handling data storage on a plurality of different types of flash devices and, in particular, to a system and method which manage the storage and retrieval of information on flash devices having different sizes of erasable units and/or read/write units, enabling them to behave as flash disks.
Flash devices include electrically erasable and programmable read-only memories (EEPROMs) made of flash-type, floating-gate transistors and are non-volatile memories similar in functionality and performance to EPROM memories, with an additional functionality that allows an in-circuit, programmable, operation to erase portions of the memory. Flash devices have the advantage of being relatively inexpensive and requiring relatively little power as compared to traditional magnetic storage disks. However, in a flash device, it is not practical to rewrite a previously written area of the memory without a preceding erase of the area. This limitation of flash devices causes them to be incompatible with typical existing operating system programs, since data cannot be written to an area of memory within the flash device in which data has previously been written, unless the area is first erased.
Software products have been proposed in the background art to allow a flash device to be managed by existing computer operating programs without modification of the operating system program. However, these background art programs all have deficiencies. For example, one program operates the flash memory as a xe2x80x9cwrite once read manyxe2x80x9d device. This background art software product cannot recycle previously written memory locations. When all locations are eventually written the memory cannot be further used without specific user intervention. To overcome these deficiencies of the background art, a flash File System (FFS) was disclosed in U.S. Pat. No. 5,404,485, which is owned in common with the present application and which is hereby incorporated by reference as if fully set forth herein. FFS provided a system of data storage and manipulation on flash devices which allowed these devices to emulate magnetic disks. As noted above, the relatively inexpensive cost and low power consumption of flash devices makes them a favorable choice for data storage, particularly for laptop, portable computers. FFS enhances the ability of flash devices to act as substitutes for magnetic disk storage. Indeed, FFS as disclosed in U.S. Pat. No. 5,404,485 has proven to be so useful that the data layout specification was adopted by the PCMCIA (Personal Computer Memory Card International Association) and JEIDA (Japan Electronic Industry Development Association) committees as a standard called Flash Translation Layer (FTL).
FFS essentially describes a virtual mapping system for flash EEPROM devices. The virtual map is a table which relates the physical address of a read/write block within the flash device to the virtual address of that block. Since each of these blocks is relatively small, 512 bytes, the size of the virtual map itself is quite large. FFS also includes a method of storing and maintaining the bulk of the virtual map on a flash EEPROM device, minimizing the amount of other memory required for storage of the virtual map.
As noted above, FFS has proven particularly successful for transforming flash devices into emulators of magnetic disk storage, so much so that it has been adopted as an industry standard. However, FFS cannot fulfill all of the requirements of the newer flash device technologies. In particular, FFS is not as successful with the NAND and AND flash technologies. Therefore, U.S. Pat. No. 5,937,425, which is owned in common with the present application and which is hereby incorporated by reference as if fully set forth herein, describes an additional implementation of the flash file system for these technologies. However, both of these implementations are useful mainly for specific types of technologies for flash memories.
For example, some new flash memory devices enable the operating software to select the exact size of the memory portion that is erased in a single erase operation. Traditional flash devices have a single size of an erase zone, which defined the chunk of data that could be erased in a single erase operation. This size was typically in the tens of kilobytes range. There are now flash devices which have more than one such erase zone size. For example, the SST34HF162X and SST34HF164X Concurrent SuperFlash devices from Silicon Storage Technology Inc. provide for erasing either 1 KWords sectors or 32 KWords blocks. Also, the NROM flash technology being developed by Saifun Semiconductors Ltd. also has this capability of being able to select the size of the erased portion from a group of two allowable sizes. This extra freedom of choice can be utilized for improving the background art methods.
The background art does not teach or suggest a mechanism for managing flash data on a plurality of different types of flash memory technologies. In addition, the background art does not teach or suggest such a mechanism which is highly flexible and which is able to operate more efficiently with these different types of technologies.
The present invention overcomes these deficiencies of the background art by providing a memory organization method which is suitable for different types of flash memory technologies.
Hereinafter, the term xe2x80x9cphysical unitxe2x80x9d is defined as a unit on the physical media or hardware of the memory which is the smallest portion of the memory which can be erased or an integral multiple thereof. It is a portion of the memory which is contiguous, fixed in size and erasable. The term xe2x80x9cphysical blockxe2x80x9d is defined as being the portion of the memory for reading or writing data.
Hereinafter, the term xe2x80x9cvirtual unitxe2x80x9d is defined as the same size as the physical unit.
Hereinafter, the term xe2x80x9cvirtual mapxe2x80x9d refers to a table which relates a virtual unit to at least one corresponding physical unit. As noted previously, each unit, virtual or physical, is composed of a plurality of blocks. The exact location of a block within a unit is determined according to one or more preset rules, as further described below.
Each physical unit is designated by a physical unit number. The location of each physical block is given by a physical block offset. Similarly, each virtual unit is designated by a virtual unit number. The location of each virtual block is given by a virtual block offset. It should be noted that each virtual unit number can correspond to one or more physical unit numbers. Thus, the mapping between virtual units and physical units can either be one-to-one or one-to-many.
Hereinafter, the term xe2x80x9cwriting dataxe2x80x9d describes the act of storing data on the flash memory. The term xe2x80x9creading dataxe2x80x9d describes the act of retrieving data from the flash memory. Hereinafter, the term xe2x80x9cunwrittenxe2x80x9d indicates some portion of the memory, such as a physical block, which is capable of having data written to it. Thus, the term xe2x80x9cunwrittenxe2x80x9d includes, but is not limited to, a portion of the memory which has just been erased.
In a computer or other electronic device having a flash memory organized according to the present invention, the operating system of that device interacts with the virtual units and virtual blocks for reading and writing data. The virtual media, which includes the virtual units and blocks, thus acts as an interface for the operating system to interact with the flash memory device. For example, the operating system issues a write command to write data to a virtual block at a virtual block offset. The virtual unit containing the virtual block is then located. The virtual map then locates a corresponding physical block within a physical unit of the memory, where the data are actually stored. Although the operating system issues read and write commands as though the virtual units and virtual blocks are the actual hardware of the flash memory, in reality the actual hardware is incorporated in the physical units and physical blocks of the flash memory. Thus, the operating system is only aware of the virtual units and blocks, and does not directly interact with the hardware itself.
The advantage of such an interface is that the inherent disadvantages of the flash memory, such as the requirement for an erase before further writing can occur, are overcome by the interactions of the operating system with the virtual memory. Additionally, the operating system of the electronic device does not have to organize the addresses of the flash memory. Furthermore, the operating system can interact with a variety of different flash memory technologies without requiring extensive modifications, since one interface can be used with multiple types of flash memory devices. Thus, the methods of the present invention permit the greatest flexibility for flash memory devices and the electronic devices which use them.
According to the present invention, there is provided a memory organization method for a memory in which data can only be written to an unwritten portion of the memory, such that a written portion of the memory must be erased to become unwritten, the memory having a plurality of memory portions for reading or writing data, each of the plurality of memory portions for reading or writing data having a size, the method comprising: providing a size of a memory portion of the memory for being erasable in one operation, wherein the size of the memory portion for erasing is selectable from a group of sizes which contains at least one size equal to the size of the memory portion for reading or writing data and which also contains at least one size being different from the size of the memory portion for reading or writing data; providing a plurality of physical units of the memory, each of the physical units being designated by a physical unit number and each of the physical units being divided into a plurality of physical blocks, each of the plurality of physical blocks being the size of the memory portion for reading or writing data and each of the physical blocks being designated by a physical block offset within the physical unit, wherein a size of the physical unit is either equal in size to one of the selectable erase sizes but not to the size of the memory portion for reading or writing, or alternatively is equal to an integral multiple of one of the selectable erase sizes, providing a plurality of virtual units of the memory, each virtual unit being designated by a virtual unit number and each of the virtual units featuring a plurality of virtual blocks being designated by a virtual block offset within the virtual unit; mapping each virtual unit to at least one physical unit to form a virtual map; and mapping each virtual block within the virtual unit to one physical block within the at least one physical unit.
According to another embodiment of the present invention, there is provided a memory organization method for a memory in which data can only be written to an unwritten portion of the memory, such that a written portion of the memory must be erased to become unwritten, and in which the size of the memory portion that can be erased in one operation differs from the size of the memory portion for reading or writing data, the method comprising: providing a plurality of physical units of the memory, each of the physical units having a size equal to an integral multiple of the smallest memory portion for erasing, each of the physical units being designated by a physical unit number and each of the physical units being divided into a plurality of physical blocks, each of the plurality of physical blocks being the size of the memory portion for reading or writing data and each of the physical blocks being designated by a physical block offset within the physical unit; providing a plurality of virtual units of the memory, each virtual unit being designated by a virtual unit number and each of the virtual units featuring a plurality of virtual blocks being designated by a virtual block offset within the virtual unit; mapping each virtual unit to at least one physical unit to form a virtual map; and mapping each virtual block within the virtual unit to one physical block within the at least one physical unit according to the virtual map.
According to still another embodiment of the present invention, there is provided a memory organization method for a memory in which data can only be written to an unwritten portion of the memory, such that a written portion of the memory must be erased to become unwritten, and in which the size of the memory portion that can be erased in one operation is selectable from a group of sizes which contains at least one size equal to the size of the memory portion for reading or writing data and which also contains at least one size larger than the size of the memory portion for reading or writing data, the method comprising: providing a plurality of physical units of the memory, each of the physical units being either equal in size to one of the selectable erase sizes but not to the size of the memory portion for reading or writing or equal to an integral multiple of any of the selectable erase sizes, each of the physical units being designated by a physical unit number and each of the physical units being divided into a plurality of physical blocks, each of the plurality of physical blocks being the size of the memory portion for reading or writing data and each of the physical blocks being designated by a physical block offset within the physical unit; providing a plurality of virtual units of the memory, each virtual unit being designated by a virtual unit number and each of the virtual units featuring a plurality of virtual blocks being designated by a virtual block offset within the virtual unit; mapping each virtual unit to at least one physical unit to form a virtual map; and mapping each virtual block within the virtual unit to one physical block within the at least one physical unit.
According to yet another embodiment of the present invention, there is provided a memory management method for a memory in which data can be written only in unwritten physical memory locations and in which a zone of contiguous memory locations can be simultaneously erased, comprising the steps of: organizing the memory into a plurality of units; organizing each unit into a plurality of blocks, each of the blocks made up of a plurality of contiguous physical memory locations; establishing an allocation map for each unit which indicates the status of each block in the unit as written, unwritten or deleted; establishing a virtual map to map virtual addresses to physical addresses; in writing data to the memory at a virtual address: mapping the virtual address to a physical address using the virtual map; examining the allocation map for the physical unit into which the virtual address has been mapped to determine the status of the physical block into which the virtual address has been mapped as written, unwritten or deleted; if the physical block is in written or deleted status, selecting one of the following two procedures: a first procedure, comprising: examining the allocation map for at least one of the units to identify an unwritten physical block; writing the data into the memory to the unwritten physical block; changing the allocation map for the unit into which the data have been written to indicate as written the previously unwritten block where the data have been written; changing the virtual map so that the virtual map maps the virtual address to the physical address of the previously unwritten block in which the data have been written; and a second procedure, comprising: erasing the physical block into which the virtual address has been mapped; writing the data into the physical block; if the physical block was previously marked as deleted in the unit allocation map, changing the allocation map for the unit into which the data have been written to indicate as written the previously deleted block where the data have been written.